package com.note.feng.leetcode.algorithms.easy.ten;

public class ThousandEightyNine {
    /**
     * 1089 复写零
     * 给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
     *
     * 注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
     *
     * 示例 1：
     *
     * 输入：arr = [1,0,2,3,0,4,5,0]
     * 输出：[1,0,0,2,3,0,0,4]
     * 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
     * 示例 2：
     *
     * 输入：arr = [1,2,3]
     * 输出：[1,2,3]
     * 解释：调用函数后，输入的数组将被修改为：[1,2,3]
     *  
     * 提示：
     *
     * 1 <= arr.length <= 104
     * 0 <= arr[i] <= 9
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/duplicate-zeros
     */
    /**
     * 解法：双指针
     * 指针 i 和指针 j 初始为 0 ，i 表示原始数组的元素位置，j 表示复写 0 后 i 对应元素的位置，
     * 当 j = len , 这时复写 0 后数组的长度不变， i 指向了原数组在复写 0 后的最后一个元素的下一个元素。
     * 此时，j 超出了数组的下标范围，需要 -- ，有 i -- 指向的元素是 0 ，j ++ 执行了 2 次，
     * 所以在交换元素的时候，j 仍有可能超出数组的下标范围。
     *
     * @param arr
     */
    public void duplicateZeros(int[] arr) {
        int i = 0,j = 0,len = arr.length;
        while (j < len) {
            if(arr[i] == 0){
                j ++;
            }
            i ++;
            j ++;
        }
        i --;
        j --;
        while (i >= 0) {
            if(j < len){
                arr[j] = arr[i];
            }
            if(arr[i] == 0 && -- j >= 0){
                arr[j] = 0;
            }
            i --;
            j --;
        }
    }
}
